// m

// 给定一个数组nums，元素值只有0,1,2，分别代表红色，白色，蓝色，将数组排序，使得红色在前，白色在中间，蓝色在最后

// 使用常数空间，一趟扫描解决

// 思路：双指针 + 快速排序
// 快速排序的partition过程，将序列中比基准数pivot大的元素移动到了基准数右侧，将比基准数pivot小的元素移动到了基准数左侧，从而将序列分为了三部分
// 比基准小的部分，基准数，比基准数大的部分
// 我们可以以1为基准，分为三部分，0,1,,2
//
// 步骤
// 1. 使用两个指针left和right，分别指向数组的头尾，left表示当前处理好的红色元素的尾部，right表示当前处理好的蓝色的头部
// 2. 再使用一个下标index遍历数组，如果遇到nums[index] === 0，就交换nums[index]和nums[left]，同时将left右移，如果遇到nums[index] === 2
// 就交换nums[index]和nums[right],同时将right左移
// 3. 直到index移动到right位置之后，停止遍历，遍历结束之后，此时left左侧都是红色，right右侧都是蓝色


// 复杂度分析
// 时间复杂度：O(n)
// 空间复杂度：O(1)
function sortColors(nums) {
    let left = 0
    let right = nums.length - 1
    let index = 0
    while (index <= right) {
        if (index < left) {
            index += 1
        } else if (nums[index] === 0) {
            [nums[index], nums[left]] = [nums[left], nums[index]]
            left += 1
        } else if (nums[index] === 2) {
            [nums[index], nums[right]] = [nums[right], nums[index]]
            right -= 1
        } else {
            index += 1
        }
    }
}

let arr = [2, 0, 2, 1, 1, 0]
sortColors(arr)
console.log(arr)